/**
 * Copyright (c) 2006-2015, JGraph Ltd
 * Copyright (c) 2006-2015, Gaudenz Alder
 */
/**
 * Class: mxGraphHierarchyModel
 *
 * Internal model of a hierarchical graph. This model stores nodes and edges
 * equivalent to the real graph nodes and edges, but also stores the rank of the
 * cells, the order within the ranks and the new candidate locations of cells.
 * The internal model also reverses edge direction were appropriate , ignores
 * self-loop and groups parallels together under one edge object.
 *
 * Constructor: mxGraphHierarchyModel
 *
 * Creates an internal ordered graph model using the vertices passed in. If
 * there are any, leftward edge need to be inverted in the internal model
 *
 * Arguments:
 *
 * graph - the facade describing the graph to be operated on
 * vertices - the vertices for this hierarchy
 * ordered - whether or not the vertices are already ordered
 * deterministic - whether or not this layout should be deterministic on each
 * tightenToSource - whether or not to tighten vertices towards the sources
 * scanRanksFromSinks - Whether rank assignment is from the sinks or sources.
 * usage
 */
function mxGraphHierarchyModel(layout, vertices, roots, parent, tightenToSource)
{
    var graph = layout.getGraph();
    this.tightenToSource = tightenToSource;
    this.roots = roots;
    this.parent = parent;

    // map of cells to internal cell needed for second run through
    // to setup the sink of edges correctly
    this.vertexMapper = new mxDictionary();
    this.edgeMapper = new mxDictionary();
    this.maxRank = 0;
    var internalVertices = [];

    if (vertices == null)
    {
        vertices = this.graph.getChildVertices(parent);
    }

    this.maxRank = this.SOURCESCANSTARTRANK;
    // map of cells to internal cell needed for second run through
    // to setup the sink of edges correctly. Guess size by number
    // of edges is roughly same as number of vertices.
    this.createInternalCells(layout, vertices, internalVertices);

    // Go through edges set their sink values. Also check the
    // ordering if and invert edges if necessary
    for (var i = 0; i < vertices.length; i++)
    {
        var edges = internalVertices[i].connectsAsSource;

        for (var j = 0; j < edges.length; j++)
        {
            var internalEdge = edges[j];
            var realEdges = internalEdge.edges;

            // Only need to process the first real edge, since
            // all the edges connect to the same other vertex
            if (realEdges != null && realEdges.length > 0)
            {
                var realEdge = realEdges[0];
                var targetCell = layout.getVisibleTerminal(
                    realEdge, false);
                var internalTargetCell = this.vertexMapper.get(targetCell);

                if (internalVertices[i] == internalTargetCell)
                {
                    // If there are parallel edges going between two vertices and not all are in the same direction
                    // you can have navigated across one direction when doing the cycle reversal that isn't the same
                    // direction as the first real edge in the array above. When that happens the if above catches
                    // that and we correct the target cell before continuing.
                    // This branch only detects this single case
                    targetCell = layout.getVisibleTerminal(
                        realEdge, true);
                    internalTargetCell = this.vertexMapper.get(targetCell);
                }

                if (internalTargetCell != null
                    && internalVertices[i] != internalTargetCell)
                {
                    internalEdge.target = internalTargetCell;

                    if (internalTargetCell.connectsAsTarget.length == 0)
                    {
                        internalTargetCell.connectsAsTarget = [];
                    }

                    if (mxUtils.indexOf(internalTargetCell.connectsAsTarget, internalEdge) < 0)
                    {
                        internalTargetCell.connectsAsTarget.push(internalEdge);
                    }
                }
            }
        }

        // Use the temp variable in the internal nodes to mark this
        // internal vertex as having been visited.
        internalVertices[i].temp[0] = 1;
    }
};

/**
 * Variable: maxRank
 *
 * Stores the largest rank number allocated
 */
mxGraphHierarchyModel.prototype.maxRank = null;

/**
 * Variable: vertexMapper
 *
 * Map from graph vertices to internal model nodes.
 */
mxGraphHierarchyModel.prototype.vertexMapper = null;

/**
 * Variable: edgeMapper
 *
 * Map from graph edges to internal model edges
 */
mxGraphHierarchyModel.prototype.edgeMapper = null;

/**
 * Variable: ranks
 *
 * Mapping from rank number to actual rank
 */
mxGraphHierarchyModel.prototype.ranks = null;

/**
 * Variable: roots
 *
 * Store of roots of this hierarchy model, these are real graph cells, not
 * internal cells
 */
mxGraphHierarchyModel.prototype.roots = null;

/**
 * Variable: parent
 *
 * The parent cell whose children are being laid out
 */
mxGraphHierarchyModel.prototype.parent = null;

/**
 * Variable: dfsCount
 *
 * Count of the number of times the ancestor dfs has been used.
 */
mxGraphHierarchyModel.prototype.dfsCount = 0;

/**
 * Variable: SOURCESCANSTARTRANK
 *
 * High value to start source layering scan rank value from.
 */
mxGraphHierarchyModel.prototype.SOURCESCANSTARTRANK = 100000000;

/**
 * Variable: tightenToSource
 *
 * Whether or not to tighten the assigned ranks of vertices up towards
 * the source cells.
 */
mxGraphHierarchyModel.prototype.tightenToSource = false;

/**
 * Function: createInternalCells
 *
 * Creates all edges in the internal model
 *
 * Parameters:
 *
 * layout - Reference to the <mxHierarchicalLayout> algorithm.
 * vertices - Array of <mxCells> that represent the vertices whom are to
 * have an internal representation created.
 * internalVertices - The array of <mxGraphHierarchyNodes> to have their
 * information filled in using the real vertices.
 */
mxGraphHierarchyModel.prototype.createInternalCells = function(layout, vertices, internalVertices)
{
    var graph = layout.getGraph();

    // Create internal edges
    for (var i = 0; i < vertices.length; i++)
    {
        internalVertices[i] = new mxGraphHierarchyNode(vertices[i]);
        this.vertexMapper.put(vertices[i], internalVertices[i]);

        // If the layout is deterministic, order the cells
        //List outgoingCells = graph.getNeighbours(vertices[i], deterministic);
        var conns = layout.getEdges(vertices[i]);
        internalVertices[i].connectsAsSource = [];

        // Create internal edges, but don't do any rank assignment yet
        // First use the information from the greedy cycle remover to
        // invert the leftward edges internally
        for (var j = 0; j < conns.length; j++)
        {
            var cell = layout.getVisibleTerminal(conns[j], false);

            // Looking for outgoing edges only
            if (cell != vertices[i] && layout.graph.model.isVertex(cell) &&
                !layout.isVertexIgnored(cell))
            {
                // We process all edge between this source and its targets
                // If there are edges going both ways, we need to collect
                // them all into one internal edges to avoid looping problems
                // later. We assume this direction (source -> target) is the
                // natural direction if at least half the edges are going in
                // that direction.

                // The check below for edges[0] being in the vertex mapper is
                // in case we've processed this the other way around
                // (target -> source) and the number of edges in each direction
                // are the same. All the graph edges will have been assigned to
                // an internal edge going the other way, so we don't want to
                // process them again
                var undirectedEdges = layout.getEdgesBetween(vertices[i],
                    cell, false);
                var directedEdges = layout.getEdgesBetween(vertices[i],
                    cell, true);

                if (undirectedEdges != null &&
                    undirectedEdges.length > 0 &&
                    this.edgeMapper.get(undirectedEdges[0]) == null &&
                    directedEdges.length * 2 >= undirectedEdges.length)
                {
                    var internalEdge = new mxGraphHierarchyEdge(undirectedEdges);

                    for (var k = 0; k < undirectedEdges.length; k++)
                    {
                        var edge = undirectedEdges[k];
                        this.edgeMapper.put(edge, internalEdge);

                        // Resets all point on the edge and disables the edge style
                        // without deleting it from the cell style
                        graph.resetEdge(edge);

                        if (layout.disableEdgeStyle)
                        {
                            layout.setEdgeStyleEnabled(edge, false);
                            layout.setOrthogonalEdge(edge,true);
                        }
                    }

                    internalEdge.source = internalVertices[i];

                    if (mxUtils.indexOf(internalVertices[i].connectsAsSource, internalEdge) < 0)
                    {
                        internalVertices[i].connectsAsSource.push(internalEdge);
                    }
                }
            }
        }

        // Ensure temp variable is cleared from any previous use
        internalVertices[i].temp[0] = 0;
    }
};

/**
 * Function: initialRank
 *
 * Basic determination of minimum layer ranking by working from from sources
 * or sinks and working through each node in the relevant edge direction.
 * Starting at the sinks is basically a longest path layering algorithm.
 */
mxGraphHierarchyModel.prototype.initialRank = function()
{
    var startNodes = [];

    if (this.roots != null)
    {
        for (var i = 0; i < this.roots.length; i++)
        {
            var internalNode = this.vertexMapper.get(this.roots[i]);

            if (internalNode != null)
            {
                startNodes.push(internalNode);
            }
        }
    }

    var internalNodes = this.vertexMapper.getValues();

    for (var i=0; i < internalNodes.length; i++)
    {
        // Mark the node as not having had a layer assigned
        internalNodes[i].temp[0] = -1;
    }

    var startNodesCopy = startNodes.slice();

    while (startNodes.length > 0)
    {
        var internalNode = startNodes[0];
        var layerDeterminingEdges;
        var edgesToBeMarked;

        layerDeterminingEdges = internalNode.connectsAsTarget;
        edgesToBeMarked = internalNode.connectsAsSource;

        // flag to keep track of whether or not all layer determining
        // edges have been scanned
        var allEdgesScanned = true;

        // Work out the layer of this node from the layer determining
        // edges. The minimum layer number of any node connected by one of
        // the layer determining edges variable
        var minimumLayer = this.SOURCESCANSTARTRANK;

        for (var i = 0; i < layerDeterminingEdges.length; i++)
        {
            var internalEdge = layerDeterminingEdges[i];

            if (internalEdge.temp[0] == 5270620)
            {
                // This edge has been scanned, get the layer of the
                // node on the other end
                var otherNode = internalEdge.source;
                minimumLayer = Math.min(minimumLayer, otherNode.temp[0] - 1);
            }
            else
            {
                allEdgesScanned = false;

                break;
            }
        }

        // If all edge have been scanned, assign the layer, mark all
        // edges in the other direction and remove from the nodes list
        if (allEdgesScanned)
        {
            internalNode.temp[0] = minimumLayer;
            this.maxRank = Math.min(this.maxRank, minimumLayer);

            if (edgesToBeMarked != null)
            {
                for (var i = 0; i < edgesToBeMarked.length; i++)
                {
                    var internalEdge = edgesToBeMarked[i];

                    // Assign unique stamp ( y/m/d/h )
                    internalEdge.temp[0] = 5270620;

                    // Add node on other end of edge to LinkedList of
                    // nodes to be analysed
                    var otherNode = internalEdge.target;

                    // Only add node if it hasn't been assigned a layer
                    if (otherNode.temp[0] == -1)
                    {
                        startNodes.push(otherNode);

                        // Mark this other node as neither being
                        // unassigned nor assigned so it isn't
                        // added to this list again, but it's
                        // layer isn't used in any calculation.
                        otherNode.temp[0] = -2;
                    }
                }
            }

            startNodes.shift();
        }
        else
        {
            // Not all the edges have been scanned, get to the back of
            // the class and put the dunces cap on
            var removedCell = startNodes.shift();
            startNodes.push(internalNode);

            if (removedCell == internalNode && startNodes.length == 1)
            {
                // This is an error condition, we can't get out of
                // this loop. It could happen for more than one node
                // but that's a lot harder to detect. Log the error
                // TODO make log comment
                break;
            }
        }
    }

    // Normalize the ranks down from their large starting value to place
    // at least 1 sink on layer 0
    for (var i=0; i < internalNodes.length; i++)
    {
        // Mark the node as not having had a layer assigned
        internalNodes[i].temp[0] -= this.maxRank;
    }

    // Tighten the rank 0 nodes as far as possible
    for ( var i = 0; i < startNodesCopy.length; i++)
    {
        var internalNode = startNodesCopy[i];
        var currentMaxLayer = 0;
        var layerDeterminingEdges = internalNode.connectsAsSource;

        for ( var j = 0; j < layerDeterminingEdges.length; j++)
        {
            var internalEdge = layerDeterminingEdges[j];
            var otherNode = internalEdge.target;
            internalNode.temp[0] = Math.max(currentMaxLayer,
                otherNode.temp[0] + 1);
            currentMaxLayer = internalNode.temp[0];
        }
    }

    // Reset the maxRank to that which would be expected for a from-sink
    // scan
    this.maxRank = this.SOURCESCANSTARTRANK - this.maxRank;
};

/**
 * Function: fixRanks
 *
 * Fixes the layer assignments to the values stored in the nodes. Also needs
 * to create dummy nodes for edges that cross layers.
 */
mxGraphHierarchyModel.prototype.fixRanks = function()
{
    var rankList = [];
    this.ranks = [];

    for (var i = 0; i < this.maxRank + 1; i++)
    {
        rankList[i] = [];
        this.ranks[i] = rankList[i];
    }

    // Perform a DFS to obtain an initial ordering for each rank.
    // Without doing this you would end up having to process
    // crossings for a standard tree.
    var rootsArray = null;

    if (this.roots != null)
    {
        var oldRootsArray = this.roots;
        rootsArray = [];

        for (var i = 0; i < oldRootsArray.length; i++)
        {
            var cell = oldRootsArray[i];
            var internalNode = this.vertexMapper.get(cell);
            rootsArray[i] = internalNode;
        }
    }

    this.visit(function(parent, node, edge, layer, seen)
    {
        if (seen == 0 && node.maxRank < 0 && node.minRank < 0)
        {
            rankList[node.temp[0]].push(node);
            node.maxRank = node.temp[0];
            node.minRank = node.temp[0];

            // Set temp[0] to the nodes position in the rank
            node.temp[0] = rankList[node.maxRank].length - 1;
        }

        if (parent != null && edge != null)
        {
            var parentToCellRankDifference = parent.maxRank - node.maxRank;

            if (parentToCellRankDifference > 1)
            {
                // There are ranks in between the parent and current cell
                edge.maxRank = parent.maxRank;
                edge.minRank = node.maxRank;
                edge.temp = [];
                edge.x = [];
                edge.y = [];

                for (var i = edge.minRank + 1; i < edge.maxRank; i++)
                {
                    // The connecting edge must be added to the
                    // appropriate ranks
                    rankList[i].push(edge);
                    edge.setGeneralPurposeVariable(i, rankList[i]
                        .length - 1);
                }
            }
        }
    }, rootsArray, false, null);
};

/**
 * Function: visit
 *
 * A depth first search through the internal heirarchy model.
 *
 * Parameters:
 *
 * visitor - The visitor function pattern to be called for each node.
 * trackAncestors - Whether or not the search is to keep track all nodes
 * directly above this one in the search path.
 */
mxGraphHierarchyModel.prototype.visit = function(visitor, dfsRoots, trackAncestors, seenNodes)
{
    // Run dfs through on all roots
    if (dfsRoots != null)
    {
        for (var i = 0; i < dfsRoots.length; i++)
        {
            var internalNode = dfsRoots[i];

            if (internalNode != null)
            {
                if (seenNodes == null)
                {
                    seenNodes = new Object();
                }

                if (trackAncestors)
                {
                    // Set up hash code for root
                    internalNode.hashCode = [];
                    internalNode.hashCode[0] = this.dfsCount;
                    internalNode.hashCode[1] = i;
                    this.extendedDfs(null, internalNode, null, visitor, seenNodes,
                        internalNode.hashCode, i, 0);
                }
                else
                {
                    this.dfs(null, internalNode, null, visitor, seenNodes, 0);
                }
            }
        }

        this.dfsCount++;
    }
};

/**
 * Function: dfs
 *
 * Performs a depth first search on the internal hierarchy model
 *
 * Parameters:
 *
 * parent - the parent internal node of the current internal node
 * root - the current internal node
 * connectingEdge - the internal edge connecting the internal node and the parent
 * internal node, if any
 * visitor - the visitor pattern to be called for each node
 * seen - a set of all nodes seen by this dfs a set of all of the
 * ancestor node of the current node
 * layer - the layer on the dfs tree ( not the same as the model ranks )
 */
mxGraphHierarchyModel.prototype.dfs = function(parent, root, connectingEdge, visitor, seen, layer)
{
    if (root != null)
    {
        var rootId = root.id;

        if (seen[rootId] == null)
        {
            seen[rootId] = root;
            visitor(parent, root, connectingEdge, layer, 0);

            // Copy the connects as source list so that visitors
            // can change the original for edge direction inversions
            var outgoingEdges = root.connectsAsSource.slice();

            for (var i = 0; i< outgoingEdges.length; i++)
            {
                var internalEdge = outgoingEdges[i];
                var targetNode = internalEdge.target;

                // Root check is O(|roots|)
                this.dfs(root, targetNode, internalEdge, visitor, seen,
                    layer + 1);
            }
        }
        else
        {
            // Use the int field to indicate this node has been seen
            visitor(parent, root, connectingEdge, layer, 1);
        }
    }
};

/**
 * Function: extendedDfs
 *
 * Performs a depth first search on the internal hierarchy model. This dfs
 * extends the default version by keeping track of cells ancestors, but it
 * should be only used when necessary because of it can be computationally
 * intensive for deep searches.
 *
 * Parameters:
 *
 * parent - the parent internal node of the current internal node
 * root - the current internal node
 * connectingEdge - the internal edge connecting the internal node and the parent
 * internal node, if any
 * visitor - the visitor pattern to be called for each node
 * seen - a set of all nodes seen by this dfs
 * ancestors - the parent hash code
 * childHash - the new hash code for this node
 * layer - the layer on the dfs tree ( not the same as the model ranks )
 */
mxGraphHierarchyModel.prototype.extendedDfs = function(parent, root, connectingEdge, visitor, seen, ancestors, childHash, layer)
{
    // Explanation of custom hash set. Previously, the ancestors variable
    // was passed through the dfs as a HashSet. The ancestors were copied
    // into a new HashSet and when the new child was processed it was also
    // added to the set. If the current node was in its ancestor list it
    // meant there is a cycle in the graph and this information is passed
    // to the visitor.visit() in the seen parameter. The HashSet clone was
    // very expensive on CPU so a custom hash was developed using primitive
    // types. temp[] couldn't be used so hashCode[] was added to each node.
    // Each new child adds another int to the array, copying the prefix
    // from its parent. Child of the same parent add different ints (the
    // limit is therefore 2^32 children per parent...). If a node has a
    // child with the hashCode already set then the child code is compared
    // to the same portion of the current nodes array. If they match there
    // is a loop.
    // Note that the basic mechanism would only allow for 1 use of this
    // functionality, so the root nodes have two ints. The second int is
    // incremented through each node root and the first is incremented
    // through each run of the dfs algorithm (therefore the dfs is not
    // thread safe). The hash code of each node is set if not already set,
    // or if the first int does not match that of the current run.
    if (root != null)
    {
        if (parent != null)
        {
            // Form this nodes hash code if necessary, that is, if the
            // hashCode variable has not been initialized or if the
            // start of the parent hash code does not equal the start of
            // this nodes hash code, indicating the code was set on a
            // previous run of this dfs.
            if (root.hashCode == null ||
                root.hashCode[0] != parent.hashCode[0])
            {
                var hashCodeLength = parent.hashCode.length + 1;
                root.hashCode = parent.hashCode.slice();
                root.hashCode[hashCodeLength - 1] = childHash;
            }
        }

        var rootId = root.id;

        if (seen[rootId] == null)
        {
            seen[rootId] = root;
            visitor(parent, root, connectingEdge, layer, 0);

            // Copy the connects as source list so that visitors
            // can change the original for edge direction inversions
            var outgoingEdges = root.connectsAsSource.slice();

            for (var i = 0; i < outgoingEdges.length; i++)
            {
                var internalEdge = outgoingEdges[i];
                var targetNode = internalEdge.target;

                // Root check is O(|roots|)
                this.extendedDfs(root, targetNode, internalEdge, visitor, seen,
                    root.hashCode, i, layer + 1);
            }
        }
        else
        {
            // Use the int field to indicate this node has been seen
            visitor(parent, root, connectingEdge, layer, 1);
        }
    }
};
